package company.qianxing_F;

import java.util.Scanner;

public class Q1A {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int maxw = sc.nextInt();
        int len = sc.nextInt();
        //价格
        int[] w = new int[len];
        //价值
        int[] v = new int[len];
        for (int i = 0; i < len; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        // 产品数 金额 价值
        // 动态规划避免递归
        // 价值
        int[][] f = new int[len + 1][maxw + 1];
        int i, j;
        //商品种类 0代表不使用
        for (i = 1; i < f.length; i++) {
            //可以使用的金额
            for (j = 1; j < f[0].length; j++) {
                //钱不够用
                if (w[i - 1] > j)
                    f[i][j] = f[i - 1][j];
                //钱够用
                else {
                    // 使用/不使用该产品 该金额下的最大价值
                    f[i][j] = Math.max(f[i - 1][j - w[i - 1]] + v[i - 1], f[i - 1][j]);
                }
            }
        }
        System.out.println(f[len][maxw]);
    }


    // 代表第几种产品 花了多少钱 最大价值
//        int[][] dp = new int[n + 1][money + 1];
//        int f[][]=new int[N+1][V+1];
    //选择第几种产品
//        for (int i = 0; i < n; i++) {
//            //用多少钱
//            for (int j = 0; j <= money; j++) {
//                //用多少个该产品
//                for (int k = 0; k * V[i] <= j; k++) {
//                    dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - k * V[i]] + k * P[i]);
//                }
//            }
//        }
//        for (int i = 0;i <= N;i++){
//            f[i][0] = 0;
//        }
//        for (int v = 0;v <= V;v++){
//            f[0][v] = 0;
//        }
//        //递推
//        for (int i = 1;i <= N;i++){
//            for (int v = 1;v <= V;v++){
//                f[i][v] = 0;
//                int nCount = v / weight[i];  //最多可以放nCount个物品i
//                //和01背包的区别就在这里，01背包只有两种状态：放与不放
//                //而完全背包可以放0到k个物品i，同样是取最大值
//                for (int k = 0;k <= nCount;k++){
//                    f[i][v] = Math.max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]);
//                }
//            }
//        }
//        return f[N][V];
//        System.out.println("最大价值为：" + dp[n][money]);
}
